import java.util.*;

public class Solution {
    Map<String,Integer> hash;
    public String[] heap;
    public int cnt;
    public boolean cmp(String s1, int k1, String s2, int k2) {
        if (k1 != k2) return k1 > k2;
        return s2.compareTo(s1) > 0;
    }

    public void shiftUp(String s, int val) {
        int parent = (cnt - 2) / 2;
        int child = cnt - 1;
        while (parent >= 0) {
            if (cmp(heap[parent], hash.get(heap[parent]), heap[child], hash.get(heap[child]))) {
                String t = heap[parent];
                heap[parent] = heap[child];
                heap[child] = t;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    public void shiftDown() {
        heap[0] = heap[cnt];
        int parent = 0;
        int child = 2 * parent + 1;
        while (child < cnt) {
            if (child + 1 < cnt && cmp(heap[child], hash.get(heap[child]), heap[child + 1], hash.get(heap[child + 1]))) child += 1;
            if (cmp(heap[parent], hash.get(heap[parent]), heap[child], hash.get(heap[child]))) {
                String t = heap[parent];
                heap[parent] = heap[child];
                heap[child] = t;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    public void add(String s, int val) {
        heap[cnt++] = s;
        if (cnt == 1) return;
        shiftUp(s,val);
    } 
    public String delete() {
        String s = heap[0];
        cnt--;
        shiftDown();
        return s;
    }
    public void createHeap(Map<String,Integer> hash, int k, List<String> list) {
        int i = 0;
        for (Map.Entry<String,Integer> entry : hash.entrySet()) {
            add(entry.getKey(), entry.getValue());
            if (cnt > k) {
                delete();
            }
        }

        while (cnt > 0) {
            list.add(delete());
        }

        Collections.reverse(list);
    }

    public List<String> topKFrequent(String[] words, int k) {
        heap = new String[k + 1];
        List<String> list = new ArrayList<>();
        hash = new HashMap<String,Integer>();
        for (int i = 0; i < words.length; i++) {
            if (hash.get(words[i]) == null) {
                hash.put(words[i],1);
            } else {
                int val = hash.get(words[i]);
                hash.put(words[i],val + 1);
            }
        }
        createHeap(hash, k, list);
        return list;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        int i = 0, j = 0;
        while (i < nums.length && i <= k) {
            if (!set.add(nums[i])) {
                return true;
            }
            i++;
        }
        i--;
        while (i < nums.length && i - j <= k) {
            set.remove(nums[j]);
            j++;
            i++;
            if (i < nums.length && !set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }
}